package com.tgy.排序;

import java.util.Arrays;

/***
 * @ClassName: InsertionSort
 * @Description: 插入排序
 * @Auther: tanggy3
 * @Date: 20:45 2022/8/15
 * @version : V1.0
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 45, 6, 2};
        //insertionStep(arr);
        int[] ints = insertionSort(arr);
        System.out.println(Arrays.toString(ints));
        int[] intArr = Utils.getIntArr();
        int[] clone = intArr.clone();
        int[] clone1 = intArr.clone();

        insertionSort(intArr);//570
        BubbleSort.fianlDeal(clone);//9598
        SelectSort.selectSortFinal(clone1);//2147
    }

    public static int[] insertionSort(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;
        int insertVal;
        int preInsertIndex;
        for (int i = 1; i < length; i++) {
            insertVal = arr[i];//取出待插的数
            preInsertIndex = i - 1;//插入下的前一个值,“有序数组”得最后一个值，待插入值必须要小于这个值才用考虑插入，不然直接放在“有序数组”的最后一个值就行了
            /**
             * 1、preInsertIndex >= 0保证在给insertVal找插入位置，不越界
             * 2、insertVal < arr[preInsertIndex]待插入的数，还没有找到插入位置
             * 3、就需要将 arr[preInsertIndex]后移
             * 满足条件代表需要向“有序数组”里插，否则直接插到最后
             */
            while (preInsertIndex >= 0 && insertVal > arr[preInsertIndex]) {
                arr[preInsertIndex + 1] = arr[preInsertIndex];//数向后（右）移
                preInsertIndex--;
            }
            if (preInsertIndex + 1 != i) {
                arr[preInsertIndex + 1] = insertVal;
            }
        }
        long l1 = System.currentTimeMillis() - l;
        System.out.println("耗时" + l1 + "ms");
        return arr;
    }


    public static int[] insertionStep(int[] arr) {
        System.out.println(Arrays.toString(arr));
        //定义待插入的数
        int insertVal = arr[1];
        int preInsertIndex = 1 - 1;//即arr[1]的前面这个数的下标
        /**
         * 1、preInsertIndex >= 0保证在给insertVal找插入位置，不越界
         * 2、insertVal<arr[preInsertIndex]待插入的数，还没有找到插入位置
         * 3、就需要将 arr[preInsertIndex]后移
         */
        while (preInsertIndex >= 0 && insertVal < arr[preInsertIndex]) {
            arr[preInsertIndex + 1] = arr[preInsertIndex];//数向后（右）移
            preInsertIndex--;
        }
        arr[preInsertIndex + 1] = insertVal;
        System.out.println("第一轮插入");
        System.out.println(Arrays.toString(arr));


        insertVal = arr[2];
        preInsertIndex = 2 - 1;
        while (preInsertIndex >= 0 && insertVal < arr[preInsertIndex]) {
            arr[preInsertIndex + 1] = arr[preInsertIndex];
            preInsertIndex--;
        }
        arr[preInsertIndex + 1] = insertVal;
        System.out.println("第二轮插入");
        System.out.println(Arrays.toString(arr));


        insertVal = arr[3];
        preInsertIndex = 3 - 1;
        while (preInsertIndex >= 0 && insertVal < arr[preInsertIndex]) {
            arr[preInsertIndex + 1] = arr[preInsertIndex];
            preInsertIndex--;
        }
        arr[preInsertIndex + 1] = insertVal;
        System.out.println("第三轮插入");
        System.out.println(Arrays.toString(arr));
        return null;
    }


}
